package day0219

func dfs(cur string, n int, result []string) {
	if len(cur) == 2*n {
		if valid(cur) {
			result = append(result, cur)
		}
		return
	}
	cur = cur + "("
	dfs(cur, n, result)
	cur = cur[:len(cur)-1]
	cur = cur + ")"
	dfs(cur, n, result)
}

func valid(str string) bool {
	balance := 0
	for i := 0; i < len(str); i++ {
		if str[i] == '(' {
			balance++
		} else {
			balance--
		}
		if balance < 0 {
			return false
		}
	}
	return balance == 0
}

func generateParenthesis(n int) []string {
	result := make([]string, 0)
	cur := ""
	dfs(cur, n, result)
	return result
}
